|
|
Vlastnosti grafů velkého obvodu
Volec, Jan ; Kráľ, Daniel (vedoucí práce) ; Sereni, Jean-Sébastien (oponent)
V práci zkoumáme dva náhodné procesy pro kubické grafy velkého obvodu. První proces nalezne pravděpodobnostní distribuci na hranových řezech takovou, že každá hrana je v náhodně vybraném řezu s pravděpodobností alespoň 0.88672. Jako důsledek odvodíme dolní odhad na velikost největšího řezu pro kubické grafy velkého obvodu a pro náhodné kubické grafy, a dále též horní odhad na váhu nejmenšího zlomkového pokrytí hranovými řezy pro kubické grafy velkého obvodu. Druhý proces nalezne pravděpodobnostní distribuci na nezavislých množinách takovou, že každý vrchol je v nezávislé množině s pravděpodobností alespoň 0.4352. Z toho plyne dolní odhad na velikost největší nezavíslé množiny pro kubické grafy velkého obvodu a pro náhodné kubické grafy, a dále též horní odhad na zlomkovou barevnost pro kubické grafy velkého obvodu.
|
|
|
Steinerovská barvení kubických grafů
Tlustá, Stanislava ; Fiala, Jiří (vedoucí práce) ; Šámal, Robert (oponent)
Tento text se zabývá barvením kubických grafů a shrnuje dostupné poznatky o tzv. Steinerovském barvení, což je hranové barvení, kde barvy stýkající se u jednoho vrcholu tvoří trojici nějakého částečného Steinerova systému. Velká pozornost je věnována zejména projektivním a afinním systémům. Následně je vyslovena postačující podmínka pro univerzalitu systému a je konstatováno, že všechny ostatní úplné tranzitivní systémy ji splňují. Součástí práce jsou také postupy vedoucí k nalezení obarvení pomocí Fanovy roviny, afinního systému Z3 3 a univerzálního systému s označením F7 S⊠ 3 vzniklého součinem Fanovy roviny s triviálním systémem. Nakonec je prezentován algoritmus použitelný pro ostatní systémy a kubické grafy s omezenou stromovou šířkou.
|
|
|
Vlastnosti grafů velkého obvodu
Volec, Jan ; Kráľ, Daniel (vedoucí práce) ; Sereni, Jean-Sébastien (oponent)
V práci zkoumáme dva náhodné procesy pro kubické grafy velkého obvodu. První proces nalezne pravděpodobnostní distribuci na hranových řezech takovou, že každá hrana je v náhodně vybraném řezu s pravděpodobností alespoň 0.88672. Jako důsledek odvodíme dolní odhad na velikost největšího řezu pro kubické grafy velkého obvodu a pro náhodné kubické grafy, a dále též horní odhad na váhu nejmenšího zlomkového pokrytí hranovými řezy pro kubické grafy velkého obvodu. Druhý proces nalezne pravděpodobnostní distribuci na nezavislých množinách takovou, že každý vrchol je v nezávislé množině s pravděpodobností alespoň 0.4352. Z toho plyne dolní odhad na velikost největší nezavíslé množiny pro kubické grafy velkého obvodu a pro náhodné kubické grafy, a dále též horní odhad na zlomkovou barevnost pro kubické grafy velkého obvodu.
|
host ::
RSS.